A ternary content-addressable memory (TCAM) is a type of memory that is designed to receive a data item that includes zeros, ones, or “*” values, and return a list of memory addresses, or a list of indices corresponding to entries of the TCAM, where the received data item is stored, if any. The “*” value may effectively be considered a mask value, or a wildcard value, such that a TCAM will return a match for a “*” value irrespective of the value being compared. TCAMs may be able to search their entire memory in one operation, making TCAMs considerably more efficient at searching than many other memory types. However, the efficient searching of TCAMs may come with the tradeoff of higher hardware and power consumption costs than those associated with other memory types.
TCAMs may be particularly well-suited for network devices that perform packet classification, such as routers, switches, etc., since these network devices often utilize network masks that effectively operate in the same manner as the mask value of the TCAM. A network device may be able to store ternary representations of all of its packet classification rules in TCAM entries, thereby allowing for an efficient lookup process for classifying packets, e.g. each TCAM entry may store a ternary representation of one packet classification rule, which may include ternary representations of one or more of: a protocol type, a source address, a destination address, a source port number, and a destination port number. For example, if the destination port range of a packet classification rule is zero through seven, then a TCAM entry containing the ternary representation of the rule may include 0000—0000—0000—0*** for the port range, when sixteen bits have been allocated to port numbers. Since the mask character matches a corresponding value of zero or a one, the destination port range portion of the example TCAM entry will match a sixteen bit representation of any destination port numbers from zero through seven.
However, it may not be possible in existing TCAM storage systems to store many of the port ranges frequently used in packet classification rules in a single TCAM entry. For example, any port range that has a lower bound greater than zero, such as the frequently used lower bound of one, would need to be stored across multiple TCAM entries, since the least significant bit of the portion of the TCAM entry corresponding to the port range must be one if all of the other bits are zero, but the least significant bit could be zero or one, if at least one of the other bits is one. For example, if the example port range discussed above were changed from zero through seven to one through seven, e.g. excluding only one additional port number (zero), the port range would require three TCAM entries, instead of only one, e.g. 0000—0000—0000—0001, 0000—0000—0000—001*, and 0000—0000—0000—01**. For similar reasons, a port range that has an upper bound that is less than 65535 may also require multiple TCAM entries. In the worst case scenario, e.g. a packet classification rule that has a port range of [1, 65534] for both the source port range and the destination port range, a total of nine hundred TCAM entries would be required to represent the packet classification rule.